#include <iostream>
#include <vector>
#include <set>

template <class T>
class PermuationGenerator
{
public:
  void add_element(T given);
  void get_permutations(std::set<std::vector<T> > *result_location);
  void generate_permutations();
  void generate_permutations(std::vector<T> done, std::set<T> remaning);
private:
  std::set<T> elements;
  std::set<std::vector<T> > result;
};

template <class T>
void PermuationGenerator<T>::add_element(T given)
{
  elements.insert(given);
}

template <class T>
void PermuationGenerator<T>::generate_permutations()
{
  std::vector<T> empty_done;
  generate_permutations(empty_done, elements);
}

template <class T>
void PermuationGenerator<T>::generate_permutations(std::vector<T> done, std::set<T> remaning)
{
  if ( remaning.empty() )
       result.insert(done);
   else
    {
      for(typename std::set<T>::iterator i = remaning.begin();
           i != remaning.end();
           i++)
        {
          std::vector<T> new_done = done;
          std::set<T> new_remaning = remaning;
          new_done.push_back(*i);
          new_remaning.erase(*i);
          
          generate_permutations(new_done, new_remaning);
        }
    }
}

template<class T>
void PermuationGenerator<T>::get_permutations(std::set<std::vector<T> > *result_location)
{
  *result_location = result;
}

// int main (int argc, char *argv[])
// {
//   PermuationGenerator<int> p;
//   p.add_element(1);
//   p.add_element(0);
//   p.add_element(2);
//   p.add_element(4);
//   p.add_element(5);
//   p.add_element(6);
//   p.add_element(7);
//   p.add_element(8);
//   p.add_element(9);
// //   p.add_element(10);

//   p.generate_permutations();
  
//   std::set<std::vector<int> > result;
//   p.get_permutations(&result);

//   for(std::set<std::vector<int> >::iterator i = result.begin();
//       i != result.end();
//       i++)
//     {
//       for(std::vector<int>::const_iterator j = i->begin();
//           j != i->end();
//           j++)
//         std::cout << *j << " ";
//       std::cout << "\n";
//     }
        
//   return 0;
// }
